/**
 * //给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * //
 * // 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子
 * //序列。
 * //
 * // 示例 1：
 * //
 * //
 * //输入：nums = [10,9,2,5,3,7,101,18]
 * //输出：4
 * //解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：nums = [0,1,0,3,2,3]
 * //输出：4
 * //
 * //
 * // 示例 3：
 * //
 * //
 * //输入：nums = [7,7,7,7,7,7,7]
 * //输出：1
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 2500
 * // -10⁴ <= nums[i] <= 10⁴
 * //
 * //
 * //
 * //
 * // 进阶：
 * //
 * //
 * // 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
 * //
 * //
 * // Related Topics 数组 二分查找 动态规划 👍 2741 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00300LongestIncreasingSubsequence {
    public static void main(String[] args) {
        Solution solution = new ID00300LongestIncreasingSubsequence().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            //dp[i]表示到达nums[i]时的最大递增子序列
//        int[] dp = new int[n];
//        dp[0] = 1;
//
//        int res = 1; //最后结果，至少为1，记录当前dp中的最大值。
//
//        for (int i = 0 ; i < n; i++){
//            dp[i] = 1; //自己先组成一个子序列
//            for(int j = 0; j < i; j++){
//                if(nums[j] < nums[i]){ // [0...i-1] 中，小于 nums[i]的 dp最大值
//                    dp[i] = Math.max(dp[j] + 1, dp[i]) ;
//                }
//            }
//            res = Math.max(dp[i], res);
//
//        }
//
//        return res;

            int res = 0; //当前长度，最后结果要+1
            //贪心算法里，dp[i]的LIS中，最小的元素
            int[] dp = new int[n];
//        dp[0] = nums[0]; //首个数字最小元素就是自己


            for (int num : nums) {
                //遍历的子查找步骤改成二分法，查找 nums[i] < dp[index];
                int a = 0;
                int b = res;

                while (a < b) { //从0 搜索到res
                    int index = (a + b) / 2;
                    if (dp[index] < num) {
                        a = index + 1;
                    } else {
                        b = index;
                    }

                }
                dp[a] = num;
                if (b == res) res++;

            }

            return res;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}